{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# The Squid Game\n",
    "## Problem definition\n",
    "YYou were out celebrating the end of the exams at EDEM and the next thing you know is you are trapped in an island playing for your life to a game known as the Squid Game. There are two players in the Squid Game, the attacker and the defender. The attacker must pass through the field, choosing one out of three possible paths, up, middle, and down. The defender must guess which path the attacker has selected, and follow the same path to meet him in the middle of the field.\n",
    "\n",
    "Both players have a limited endurance, measured in endurance points, and start with 10 endurance points. The winner is the player that resists the longest time without loosing all endurance points.\n",
    "\n",
    "The field is fraught with traps that cause injuries to the players. If the attacker crosses the 'up' or 'down' paths, the damage caused to the attacker is assessed as -3 endurance points. If the attacker chooses the 'middle' path, the damage is assessed as -1 endurance points. If the defender chooses the 'up' or 'down' paths,the damage is -1 endurance points. The damage for the defender is -3 endurance points if he chooses the middle path.\n",
    "\n",
    "Both players are blindfolded and choose the path they would like to follow at the same time. If the defender chooses the same path as the attacker, the damage for the attacker is -5 endurance points. If on the other hand the defender chooses a different path, the damage for the defender is -2 endurance points. The following image shows the Squid Game field and the damage in storage points in each path.\n",
    "\n",
    "![squid game](img/squid_game.png)\n",
    "\n",
    "**a)** Write down the tabular representation of the game.\n",
    "Let us note the Attacker as Player A and the defender as Player B. The tabular representation, noting the first value of the tuple is the gain for player A and the second value after the slash is the value for player B is:\n",
    "\n",
    "| Player A / B | Up         | Middle     | Down       |\n",
    "|--------------|------------|------------|------------|\n",
    "| Up           | -3-5=-8/-1 | -3/-3-2=-5 | -3/-1-2=-3 |\n",
    "| Middle       | -1/-1-2=-3 | -1-5=-6/-3 | -1/-1-2=-3 |\n",
    "| Down         | -3/-1-2=-3 | -3/-3-2=-5 | -3-5=-8/-1 |\n",
    "\n",
    "In short:\n",
    "\n",
    "| Player A / B | Up    | Middle | Down  |\n",
    "|--------------|-------|--------|-------|\n",
    "| Up           | -8/-1 | -3/-5  | -3/-3 |\n",
    "| Middle       | -1/-3 | -6/-3  | -1/-3 |\n",
    "| Down         | -3/-3 | -3/-5  | -8/-1 |\n",
    "\n",
    "**b)** Find the move each player would choose following the minmax criteria. Discuss briefly if there is equilibrium.\n",
    "Applying the min max criteria, we add a new column to note the worst case scenario for each alternative of player A, and a new row to note the worst case alternative for each alternative of player B.\n",
    "\n",
    "| Player A / B | Up    | Middle | Down  | min |\n",
    "|--------------|-------|--------|-------|-----|\n",
    "| Up           | -8/-1 | -3/-5  | -3/-3 | -8  |\n",
    "| Middle       | -1/-3 | -6/-3  | -1/-3 | -6  |\n",
    "| Down         | -3/-3 | -3/-5  | -8/-1 | -8  |\n",
    "| Min          | -3    | -5     | -3    |     |\n",
    "\n",
    "Player A would select the Middle as it provides the maximum value across the three worst case scenarios (-6). \n",
    "Player B would select either up or down since they both provide the minimum value (-3). The problem does not have equilibrium, since player B will probably would like to change strategy after few moves.\n",
    "\n",
    "**c)** Now think of the game as a zero-sum game where the gain in each move is the difference in damage points between the attacker and the defender for each combination of pairs of paths selected. Write down the linear programming problems to calculate the optimal probabilities of the mixed strategies for both players.\n",
    "\n",
    "| Player a / A | Up  | Middle | Down |\n",
    "|--------------|-----|--------|------|\n",
    "| Up           | 7   | -2     | 0    |\n",
    "| Middle       | -2  | 3      | -2   |\n",
    "| Down         | 0   | -2     | 7    |\n",
    "\n",
    "Let us add a constant ($k=2$) to create an equivalent problem where all the values are positive:\n",
    "\n",
    "| Player a / A | Up  | Middle | Down |\n",
    "|--------------|-----|--------|------|\n",
    "| Up           | 9   | 0      | 2    |\n",
    "| Middle       | 0   | 5      | 0    |\n",
    "| Down         | 2   | 0      | 9    |\n",
    "\n",
    "Now, the following CLP problem is used to calculate the probabilities of player A:\n",
    "\n",
    "$\\max z = x_1 + x_2 + x_3$\n",
    "\n",
    "$9*x_1 + 0*x_2 + 2*x_3 \\leq 1$\n",
    "\n",
    "$0*x_1 + 5*x_2 + 0*x_3 \\leq 1$\n",
    "\n",
    "$2*x_1 + 0*x_2 + 9*x_3 \\leq 1$\n",
    "\n",
    "The strategy for Player B is obtained with the dual problem:\n",
    "\n",
    "$\\min z = u_1 + u_2 + u_3$\n",
    "\n",
    "$9*u_1 + 0*u_2 + 2*u_2 \\geq 1$\n",
    "\n",
    "$0*u_1 + 5*u_2 + 0*u_3 \\geq 1$\n",
    "\n",
    "$2*u_1 + 0*u_2 + 9*u_3 \\geq 1$\n",
    " "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}